﻿using System;
using ClearSpringNet.Hash;

namespace ClearSpringNet.Stream.Cardinality
{
    /// <summary>
    /// Implementationt of HyperLogLog in C#
    /// Author:Jeremy Woo 
    ///
    /// http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
    /// 
    /// The creator of this algorithm passed away in 2011 (not me) 
    /// 
    /// 
    /// for v e M do
    /// set x := h(v);
	/// set j = 1 + (x1x2x3...xb)2  {the binary address determined by the ﬁrst b bits of x}
	/// set w := xb+1xb+2.....; set M[j] := max(M[j], alpha(w));
    /// Compute Z = Sum(j=1, to M) 2 power -M[j]
    /// Return = alpha(m)M power 2 Z 
    /// 
    /// Example usage:
    /// ------------------------------------------------------------------------------------------------------
    /// var log_log = new HyperLogLog(0.065);
    /// var words = new[] { "aardvark", "aardvark", "aardvark", "abyssinian", "zoology", "aardvark" }; 
    /// var seed = Math.Floor((double) log_log.MaxPower); // make more fun
    ///
    // for (var i = 0; i < words.Length; ++i)
    // {
    //   var key = HyperLogLog.fnv1a(words[i]) ^ (uint) seed; 
    //   log_log.StreamInKey((int) key);
    // }
    //
    //  var res = log_log.GetItemCount();
    // .
    //  ------------------------------------------------------------------------------------------------------
    /// </summary>
    public class HyperLogLog
    {
        private readonly double _stdError;
        private double m;
        private double k;
        private int k_comp;
        private double alpha_m;
        private double[] M;
        private const uint MaxUnsignedIntValue = uint.MaxValue;

        public uint MaxPower
        {
            get { return MaxUnsignedIntValue; }
        }

        public HyperLogLog(double stdError)
        {
            _stdError = stdError;
            InitializationVariables();
        }

        public void StreamInKey(int hash)
        {
            var j = (uint)hash >> k_comp;
            M[j] = Math.Max(M[j], Rank(hash, k_comp));
        }

        public bool GetKey(string key)
        {
            var j = GetHashKey(key);
            return M[j] != 0;
        }

        /// <summary>
        /// Retrieve the total number of distinct item found in a collections. 
        /// This is suppose to be super fast! 
        /// </summary>
        /// <returns></returns>
        public double GetItemCount()
        {
            var c = 0.0;
            for (var i = 0; i < m; ++i) c += 1 / Math.Pow(2, M[i]);
            var E = alpha_m * m * m / c;

            if (E <= 5 / 2 * m)    // Small range correction.
            {
                var V = 0;
                for (var i = 0; i < m; ++i) if (M[i] == 0) ++V;
                if (V > 0) E = m * Math.Log(m / V);
            }
            else if (E > 1 / 30 * MaxUnsignedIntValue)  // Large range correction,. 
                E = -MaxUnsignedIntValue * Math.Log(1 - E / MaxUnsignedIntValue);

            return E;   // Intermediate range correction.
        }

        /// <summary>
        ///  Glenn Fowler, Landon Curt Noll, and Phong Vo hashing.
        /// </summary>
        /// <param name="text"></param>
        /// <returns></returns>
        public static uint fnv1a(string text)
        {
            return new FowlerNollVoHash().Hash(text);
        }

        private static double Log2(double x)
        {
            return Math.Log(x, 2);  // x = value // 2 is the base 
        }


        private static int Rank(int hash, int max)
        {
            var rank = 1;
            while ((hash & 1) == 0 && rank <= max) { ++rank; hash >>= 1; }
            return rank;
        }

        /// <summary>
        /// Initalize variables and constants. 
        /// </summary>
        private void InitializationVariables()
        {
            m = 1.04 / _stdError;
            k = Math.Ceiling(Log2(m * m));
            k_comp = Convert.ToInt32(32 - k);
            m = Math.Pow(2, k);
            alpha_m = m == 16 ? 0.673 : m == 32 ? 0.697 : m == 64 ? 0.709 : 0.7213 / (1 + 1.079 / m);

            M = new double[(int)m];

            for (var i = 0; i < m; ++i)
                M[i] = 0;
        }

        private uint GetHashKey(string key)
        {
            var seed = Math.Floor((double)MaxUnsignedIntValue);
            var hash = fnv1a(key) ^ (uint)seed;
            return hash >> k_comp;
        }
    }
}